package com.qisi.kandroidshalon.leetcode.sort;

import android.util.Log;

import com.qisi.kandroidshalon.leetcode.Util;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * 桶排序
 */
public class RadixSort {

    private static final String TAG = "LeetCodeUtil";

    /**
     * 桶排序
     *
     * @param arr
     */
    public static void radixSort(Integer[] arr) {
        int maxDigit = maxDigit(arr);
        int[] bucketRanges = new int[10];//bucket[index]存放digit=index的个数，然后在做前缀和处理，bucket[index]存放digit<=index的个数，用以划分这个数在数组中的范围
        int[] bucketContainer = new int[arr.length];
        //从个位开始计算,每一位执行一次桶排序
        for (int digitIndex = 0; digitIndex < maxDigit; digitIndex++) {//先取低位

            for (int i = 0; i < arr.length; i++) {
                int d = getDigit(arr[i], digitIndex);
                //对应的位数++
                bucketRanges[d]++;
            }
            Log.i(TAG, "Step1: 频率计数");
            Util.dumpArray(bucketRanges);
            for (int i = 1; i < bucketRanges.length; i++) {
                bucketRanges[i] += bucketRanges[i - 1];//bucketRanges[i]=对应位数小于等于i的个数，相当于划定范围
            }

            Log.i(TAG, "Step2: 桶范围划定");
            Util.dumpArray(bucketRanges);
            //数据入桶, todo 注意分配桶需要从右边开始，因为索引是--的，需要先放大数，这样才能保证上次的排序结果不乱
            for (int i = arr.length - 1; i >= 0; i--) {
                int d = getDigit(arr[i], digitIndex);
                //写入一个数据后，范围--
                int targetIndex = --bucketRanges[d];
                bucketContainer[targetIndex] = arr[i];
            }
            //清除桶边界
            Arrays.fill(bucketRanges, 0);
            //数据出桶
            for (int i = 0; i < arr.length; i++) {
                arr[i] = bucketContainer[i];
            }
            Log.i(TAG, "Step3: 分配桶结果");
            Util.dumpArray(arr);
        }

    }


    /**
     * 求数组的最大位数
     *
     * @param arr
     * @return
     */
    private static int maxDigit(Integer[] arr) {
        int max = Util.max(arr);
        int digit = 0;
        while (max > 0) {
            digit++;
            max = max / 10;
        }
        return digit;
    }

    private static int getDigit(int num, int low) {
        int pow = (int) Math.pow(10, low);
        int d = (num / pow) % 10;
        return d;
    }

}
